import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1619. 删除某些元素后的数组均值
 * https://leetcode-cn.com/problems/mean-of-array-after-removing-some-elements/
 */
public class Solutions_1619 {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3};  // output: 2.00000
        int[] arr2 = {6, 2, 7, 5, 1, 2, 0, 3, 10, 2, 5, 0, 5, 5, 0, 8, 7, 6, 8, 0};  // output: 4.00000
        int[] arr3 = {6, 0, 7, 0, 7, 5, 7, 8, 3, 4, 0, 7, 8, 1, 6, 8, 1, 1, 2, 4, 8, 1, 9, 5, 4, 3, 8, 5, 10, 8, 6, 6, 1, 0, 6, 10, 8, 2, 3, 4};  // output: 4.77778
        int[] arr4 = {9, 7, 8, 7, 7, 8, 4, 4, 6, 8, 8, 7, 6, 8, 8, 9, 2, 6, 0, 0, 1, 10, 8, 6, 3, 3, 5, 1, 10, 9, 0, 7, 10, 0, 10, 4, 1, 10, 6, 9, 3, 6, 0, 0, 2, 7, 0, 6, 7, 2, 9, 7, 7, 3, 0, 1, 6, 1, 10, 3};  // output: 5.27778
        int[] arr5 = {4, 8, 4, 10, 0, 7, 1, 3, 7, 8, 8, 3, 4, 1, 6, 2, 1, 1, 8, 0, 9, 8, 0, 3, 9, 10, 3, 10, 1, 10, 7, 3, 2, 1, 4, 9, 10, 7, 6, 4, 0, 8, 5, 1, 2, 1, 6, 2, 5, 0, 7, 10, 9, 10, 3, 7, 10, 5, 8, 5, 7, 6, 7, 6, 10, 9, 5, 10, 5, 5, 7, 2, 10, 7, 7, 8, 2, 0, 1, 1};  // output: 5.29167

        List<int[]> inputs = new ArrayList<>();
        inputs.add(arr1);
        inputs.add(arr2);
        inputs.add(arr3);
        inputs.add(arr4);
        inputs.add(arr5);

        for (int[] input : inputs) {
            double result = trimMean(input);
            System.out.println(result);
        }
    }

    public static double trimMean(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        int cnt = len / 20;
        int sum = 0;
        for (int i = cnt; i < len - cnt; i++) {
            sum += arr[i];
        }
        return (double) sum / (len - 2 * cnt);
    }
}
